package org.basic.algorithm.simple.offer;

/**
 * 给定两个整数 a 和 divide ，求它们的除法的商 a/divide ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 * <p>
 * 注意：
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
 * <p>
 * 示例 1：
 * 输入：a = 15, divide = 2
 * 输出：7
 * 解释：15/2 = truncate(7.5) = 7
 * <p>
 * 示例 2：
 * 输入：a = 7, divide = -3
 * 输出：-2
 * 解释：7/-3 = truncate(-2.33333..) = -2
 * <p>
 * 示例 3：
 * 输入：a = 0, divide = 1
 * 输出：0
 *
 * @author LiKun
 * @date 2021/10/26 14:37
 */
public class Xoh6Oh {
    public static void main(String[] args) {
        System.out.println(divide(123, 3));     // 1001  0010
    }

    public static int divide(int a, int b) {
        long dividend, divide, count, result = 0;
        boolean flag = (a > 0 && b > 0) || (a < 0 && b < 0);

        if (b == 1 || b == -1) {
            result = (b == 1) ? a : -((long) a);
        } else {
            divide = b > 0 ? b : -((long) b);
            dividend = a > 0 ? a : -((long) a);

            while (dividend >= divide) {
                count = 0;
                while ((divide << count + 1) <= dividend) {
                    count++;
                }

                result += flag ? 1L << count : -(1L << count);
                dividend -= divide << count;
            }
        }

        return result < Integer.MIN_VALUE || result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result;
    }
}
